CSE 373: Data Structures and Algorithms

Winter 2000

Assignment 1 Chapter 2 Solutions

1. Exercise 2.6 (a) [exercise 2.7 (a) in the C++ book]

You need to explain your analysis if you don't give a tight bound,

(1) O(N)

(2) O(N^2)

(3) O(N^3)

(4) O(N^2)

(5) O(N^5)

(6) O(N^4)

2. Exercise 2.8 [exercise 2.9 in the C++ book]

Algorithm        1        2        3        4
                O(N^3)  O(N^2)    O(NlogN)  O(N)
N=10,000       440,000
N=100,000      4*10^8   1*10^4
N=10^6         4*10^11  1*10^6    95       2.9

for the 1st algorithm, as N increases by 10 times, the running time should increase by 10^3 times. similar for the rest of the algorithms. the second algorithm should increase 10^2 times. for the 3rd algorithm increases 10*n/(n-1) times, where N=10^n. the 4th increases 10 times.

3. Exercise 2.12 [exercise 2.17 (a) in the C++ book]

Given as pseudocode, not exactly in C++/C syntax.

int MinSubSum(const int A[], int N) {

int ThisSum, MinSum, j;

ThisSum = MinSum = 0;

for (j = 0; j <= N; j++)

{

ThisSum += A[j];

if (ThisSum < MinSum)

MinSum = ThisSum;

else if (ThisSum > 0)

ThisSum = 0

}

return MinSum

}

Time complexity O(N)

int MinPosSubSum(int A[], int N) {

int ThisSum, MinSum, i, j, k;

// initialize MinSum to the largest value in the whole array

// the reason is that if we initialize MinSum to 0, then MinPosSubSum will

// alway return 0

MinSum = A[0]

for (i = 1; i < N; i++) {

if (A[i] > MinSum)

MinSum = A[i];

}

for (i = 0; i < N; i++)

for (j = i; j < N; j++) {

ThisSum = 0;

for (k = i; k <= j; k++)

ThisSum += A[k];

if (ThisSum < MinSum && ThisSum > 0)

MinSum = ThisSum;

}

return MinSum;

}

Time complexity O(N^3)

int MaxSubProd(int A[], int N) {

int ThisProd, MaxProd, i, j, k;

// initialize MinSum to the largest value in the whole array

// the reason is that if we initialize MinSum to 0, then MinPosSubSum will

// alway return 0

MaxProd = A[0]

for (i = 1; i < N; i++) {

if (A[i] > MaxProd)

MaxProd = A[i];

}

for (i = 0; i < N; i++)

for (j = i; j < N; j++) {

ThisProd = 1;

for (k = i; k <= j; k++)

ThisProd *= A[k];

if (ThisProd < MaxProd && ThisProd > 0)

MaxProd = ThisProd;

}

return MaxProd;

}

Time complexity O(N^3)

4. Exercise 2.16 [exercise 2.23 in the C++ book]

as pseudo code

acc = 1;

y = x;

while (true) {

if (n = 0) return 1;

if (n = 1) return acc * y;

if iseven(n)

y = y * y;

else

acc = y * acc;

y = y * y;

n = n/2;

}

5. Exercise 2.18 [exercise 2.25 in the C++ book]

a. A.
b. B.
c. unknown. we don't know what's the average running time of the two algorithms.
d. impossible. In worst cases, B will run much slower than A when N gets really big as determined by their big-O analysis.

6. Various programming environments provide a function for copying memory between two locations (e.g., strncpy(src, dst, size) in C). However, these routines do not always take into account the situation where src and dst overlap. For example, if src = 1000 and dst = 1050 and size = 100 the last half of src overlaps with the first half of dst. If src and dst are reversed in the above example the overlap is just opposite. Provide a convincing argument why the following code fragment for copying strings is buggy and then give the corrected code fragment (assume that dst and src are declared “char *”.)

for (i=0; i < size; i += 1) { dst[i] = src[i]);}

The bug is that the second half of the source will be overwritten with values in the first half before it gets copied to dest. So the second half of the destination will get wrong values.
solution:
if (src<dest)
    for (int i=size-1;i>=0;i--)
        dest[i]=src[i];
else for (int i=0;i<size;i++)
         dest[i]=src[i];

7. [Not graded] How much time did you spend on this homework assignment? On a scale from 1 to 10 (1 being way too easy, 5 being just about right, and 10 being way too hard) how would you rate this for a weekly homework assignment?